package 牛客_面试必刷.Month07.day08;

import java.util.Stack;

public class 链表中的节点每K个一组翻转 {
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        if(head == null || k < 1) return head;//首先排除一些特殊情况
        ListNode res = new ListNode(0);//构造一个虚拟节点用来拼接反转后的部分
        ListNode myres = res;
        Stack<ListNode> stack = new Stack<>();//用栈来进行翻转
        while(true){
            for (int i = 0;i < k; i++) {//首先就是入栈，每K个是一组
                stack.push(head);
                head = head.next;
                if(head == null) break;//如果说当前的所剩个数小于K，那么就直接break
            }
            if(stack.size() == k){//如果说此时栈内元素恰好等于K
                while(!stack.isEmpty()){//那么就进行链表的反转
                    myres.next = stack.pop();
                    myres = myres.next;
                    myres.next = null;
                }
            }
            //如果说此时链表的倍数恰好为K，也是break
            if(head == null) break;//这里是防止链表长度恰好是k的整数倍
        }
        //然后这里处理一下栈内元素大于0小于K的情况
        ListNode end = null;
        while(!stack.isEmpty()){
            end = stack.pop();
        }
        myres.next = end;
        return res.next;
    }
}
